package com.github.yangyishe;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 字符串中的查找与替换
 * https://leetcode.cn/problems/find-and-replace-in-string/
 * The type Problem 180.
 * 你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出：indices, sources,  targets。
 *
 * 要完成第 i 个替换操作:
 *
 * 检查 子字符串  sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。
 * 如果没有出现， 什么也不做 。
 * 如果出现，则用 targets[i] 替换 该子字符串。
 * 例如，如果 s = "abcd" ， indices[i] = 0 , sources[i] = "ab"， targets[i] = "eee" ，那么替换的结果将是 "eeecd" 。
 *
 * 所有替换操作必须 同时 发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。
 *
 * 例如，一个 s = "abc" ，  indices = [0,1] ， sources = ["ab"，"bc"] 的测试用例将不会生成，因为 "ab" 和 "bc" 替换重叠。
 * 在对 s 执行所有替换操作后返回 结果字符串 。
 *
 * 子字符串 是字符串中连续的字符序列。
 *
 *
 *
 * 示例 1：
 * https://assets.leetcode.com/uploads/2021/06/12/833-ex1.png
 *
 *
 * 输入：s = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
 * 输出："eeebffff"
 * 解释：
 * "a" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
 * "cd" 从 s 中的索引 2 开始，所以它被替换为 "ffff"。
 *
 * 示例 2：
 * https://assets.leetcode.com/uploads/2021/06/12/833-ex2-1.png
 *
 * 输入：s = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
 * 输出："eeecd"
 * 解释：
 * "ab" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
 * "ec" 没有从原始的 S 中的索引 2 开始，所以它没有被替换。
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 1000
 * k == indices.length == sources.length == targets.length
 * 1 <= k <= 100
 * 0 <= indexes[i] < s.length
 * 1 <= sources[i].length, targets[i].length <= 50
 * s 仅由小写英文字母组成
 * sources[i] 和 targets[i] 仅由小写英文字母组成
 */
public class Problem833 {
    public static void main(String[] args) {
        Problem833 problem833 = new Problem833();
        String s="vmokgggqzp";
        int[] indexes=new int[]{3,5,1};
        String[] sources=new String[]{"kg","ggq","mo"};
        String[] targets=new String[]{"s","so","bfr"};

        String replaceString = problem833.findReplaceString(s, indexes, sources, targets);
        System.out.println(replaceString);
    }

    public String findReplaceString1(String s, int[] indices, String[] sources, String[] targets) {

        int[] ints = Arrays.stream(indices).sorted().toArray();
        Map<Integer,String> index2SourceMap=new HashMap<>();
        Map<Integer,String> index2TargetMap=new HashMap<>();
        for (int i = 0; i < indices.length; i++) {
            int index = indices[i];
            String source = sources[i];
            String target = targets[i];
            index2SourceMap.put(index,source);
            index2TargetMap.put(index,target);
        }
        int addIndex=0;
        for (int i = 0; i < ints.length; i++) {
            int index = ints[i];
            String source = index2SourceMap.get(index);
            String target = index2TargetMap.get(index);
            int preIndex = index + addIndex;
            int postIndex = index + addIndex + source.length();
            String oldStr = s.substring(preIndex, postIndex);
            boolean equSrc = oldStr.equals(source);
            if (equSrc) {
                s=s.substring(0, preIndex)+target+s.substring(postIndex);
                addIndex+=target.length()-source.length();
            }
        }


        return s;
    }

    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {

        String[] replaceStrs=new String[s.length()];
        int[] replaceLens=new int[s.length()];
        Arrays.fill(replaceLens,1);

        for (int i = 0; i < indices.length; i++) {
            int index = indices[i];
            String source = sources[i];
            String target = targets[i];
            if (s.startsWith(source,index)) {
                replaceLens[index]=source.length();
                replaceStrs[index]=target;
            }
        }

        StringBuilder stringBuilder=new StringBuilder("");
        for (int i = 0; i < s.length(); i+=replaceLens[i]) {
            String replaceStr = replaceStrs[i];
            if (replaceStr!=null) {
                stringBuilder.append(replaceStr);
            }else{
                // 此时length==1
                stringBuilder.append(s.charAt(i));
            }

        }

        return stringBuilder.toString();
    }
}
